package com.geticsen.leetcode;

//https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
public class Solution_121 {
    public int maxProfit(int[] prices) {
        //贪心算法找左边最小的 然后用后面的减去这个最小值找出利润最大
        int low_left = Integer.MAX_VALUE;
        int result = 0;
        for (int price : prices) {
            low_left = Math.min(price, low_left);
            result = Math.max(result, price - low_left);
        }
        return result;
    }

    public int maxProfit1(int[] prices) {
        //暴力搜索
        int max = -1;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (max < prices[j] - prices[i]) {
                    max = prices[j] - prices[i];
                }
            }
        }
        return max == -1 ? 0 : max;
    }
}
